package com.gyx.rocsun.bootstrap;

import java.util.*;

/**
 * @program: rocsun
 * @description:
 * @author: yx.guo
 * @create: 2024-12-10 19:40
 **/
public class Test {

    public static int trap(int[] height) {
        int leftMax = 0;
        int rightMax = 0;
        int left = 0;
        int right = height.length - 1;

        int ans = 0;

        while (left < right) {
            leftMax = Math.max(height[left], leftMax);
            rightMax = Math.max(height[right], rightMax);
            if (leftMax > rightMax) {
                // 计算右边最大值月当前左边积水
                ans += rightMax - height[right];
                right--;
                System.out.println("left > right: " + (leftMax > rightMax));
            } else {
                // 计算左边最大值月当前右边积水
                ans += leftMax - height[left];
                left++;
                System.out.println("left <= right: " + (leftMax <= rightMax));
            }
        }

        return ans;
    }

    static Map<Character, Integer> symbolValues = new HashMap<Character, Integer>() {{
        put('I', 1);
        put('V', 5);
        put('X', 10);
        put('L', 50);
        put('C', 100);
        put('D', 500);
        put('M', 1000);
    }};

    static Map<Integer, String> valueSymbol = new HashMap<Integer, String>() {{
        put(1, "I");
        put(4, "IV");
        put(5, "V");
        put(9, "IX");
        put(10, "X");
        put(40, "XL");
        put(50, "L");
        put(90, "XC");
        put(100, "C");
        put(400, "CD");
        put(500, "D");
        put(900, "CM");
        put(1000, "M");
    }};

    public static int romanToInt(String s) {
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            ans += i + 1 < s.length() && symbolValues.get(s.charAt(i)) < symbolValues.get(s.charAt(i + 1)) ?
                    -symbolValues.get(s.charAt(i)) : symbolValues.get(s.charAt(i));
        }

        return ans;
    }

    public static String intToRoman(int num) {
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] rom = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < values.length; i++) {
            while (num > values[i]) {
                num -= values[i];
                sb.append(rom[i]);
            }
        }
        return sb.toString();
    }

    public static int lengthOfLastWord(String s) {
        int length = 0;
        s = s.trim();
        for (int i = s.length() - 1; i >= 0; i--) {
            if (!" ".equals(Character.toString(s.charAt(i)))) {
                length++;
            } else {
                return length;
            }
        }

        return s.length();
    }

    public static String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        if (strs.length == 1) return strs[0];

        // 寻找所有字符串的公共子串，就等于寻找每两个元素的子串，然后寻找字串与第三个元素的子串
        String prefix = strs[0];

        for (int i = 1; i < strs.length; i++) {
            if (strs[i].isEmpty()) {
                return "";
            }

            if (!strs[i].startsWith(prefix)) {
                int len = Math.min(prefix.length(), strs[i].length());

                int n = 0;
                for (int j = 0; j < len; j++) {
                    if (prefix.charAt(j) != strs[i].charAt(j)) {
                        break;
                    }
                    n++;
                }
                prefix = prefix.substring(0, n);
            }
        }

        return prefix;
    }

    private static String longestCommonPrefix(String prefix, String item) {
        int len = Math.min(prefix.length(), item.length());

        int n = 0;
        for (int i = 0; i < len; i++) {
            if (prefix.charAt(i) != item.charAt(i)) {
                break;
            }
            n++;
        }

        return prefix.substring(0, n);
    }

    public static String longestCommonPrefix1(String[] strs) {
        if (strs.length == 0) return "";
        if (strs.length == 1) return strs[0];

        int size = strs.length;
        int len = strs[0].length();

        int n = 0;
        for (int i = 0; i < len; i++) {
            char a = strs[0].charAt(i);
            for (int j = 1; j < size; j++) {
                if (i == strs[j].length() || a != strs[j].charAt(i)) {
                    return strs[0].substring(0, n);
                }
            }
            n++;
        }

        return strs[0];
    }

    /**
     * 将一个句子中的单词调转顺序显示，其中包含空格
     * @param s
     * @return
     */
    public static String reverseWords(String s) {
        int fast = 0;
        int slow = 0;
        List<String> wordList = new ArrayList<String>();

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ' ') {
                if (fast == slow) {
                    fast = i + 1;
                    slow = fast;
                } else {
                    wordList.add(s.substring(slow, fast));
                    slow = i + 1;
                    fast = slow;
                }
            } else {
                fast++;
            }
        }

        // 补充一下因为循环介绍书而导致的最
        if (fast > slow) {
            wordList.add(s.substring(slow, fast));
        }

        StringBuilder sb = new StringBuilder();
        for (int i = wordList.size() - 1; i >= 0 ; i--) {
            sb.append(wordList.get(i)).append(" ");
        }
        return sb.toString();
    }

    /**
     *  Z 字形变换问题
     * @param s
     * @param numRows
     * @return
     */
    public static String convert(String s, int numRows) {
        if (s.length() == 1 || numRows == 1) {
            return s;
        }
        List<StringBuilder> numList = new ArrayList<StringBuilder>();
        for (int i = 0; i < numRows; i++) {
            numList.add(new StringBuilder());
        }

        int length = s.length();
        int flag = -1;
        int n = 0;
        for (int i = 0; i < length; i++) {
            if (i % (numRows -1) == 0) {
                flag = flag * -1;
            }
            numList.get(n).append(s.charAt(i));
            n = n + flag;
        }

        StringBuilder sb1 = new StringBuilder();
        numList.forEach(sb1::append);

        return sb1.toString();
    }

    /**
     *  Z 字形变换问题
     * @param s
     * @param numRows
     * @return
     */
    public static String zConvert(String s, int numRows) {
        if (s.length() == 1 || numRows == 1) return s;
        int len = s.length();
        // 根据行数可以得到第一行和最后一行间隔
        int space = 2 * (numRows - 1);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < numRows; i++) {
            for (int j = i; j < len; j+=space) {
                sb.append(s.charAt(j));
                if (i != 0 && i != numRows - 1 && j + space - 2 * i < len) {
                    sb.append(s.charAt(j + space - 2 * i));
                }
            }
        }

        return sb.toString();
    }


    public static void main(String[] args) {
//        int[] a = {0,1,0,2,1,0,1,3,2,1,2,1};
//        int[] b = {3, 4, 3};
//        System.out.println(trap(a));
//        System.out.println(romanToInt(""));
//        System.out.println(intToRoman(3287));
//        System.out.println(lengthOfLastWord("   fly me   to   the moon  "));
//        String[] strs = {"ab","abc","a"};
//        System.out.println(longestCommonPrefix1(strs));
//        System.out.println(reverseWords("the sky is blue"));
//          System.out.println(convert("PAYPALISHIRING", 3));
//        System.out.println(zConvert("PAYPALISHIRING", 3));
//        System.out.println(divide(2147483647, 2));
//        System.out.println(divide(2147483647, 3));
//        String[] words = {"Listen","to","many,","speak","to","a","few."};
//        fullJustify(words, 6).forEach(System.out::println);
//        System.out.println(isPalindrome("A man, a plan, a canal: Panama"));

//        System.out.println(isSubsequence("twn", "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxtxxxxxxxxxxxxxxxxxxxxwxxxxxxxxxxxxxxxxxxxxxxxxxn"));

//        System.out.println(Arrays.toString(buildTable("aazbdz")));
//        System.out.println(isSubsequence_DP("twn", "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxtxxxxxxxxxxxxxxxxxxxxwxxxxxxxxxxxxxxxxxxxxxxxxxn"));
//        System.out.println(isSubsequence_Binary("twn", "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxtxxxxxxxxxxxxxxxxxxxxwxxxxxxxxxxxxxxxxxxxxxxxxxn"));
//        List<Integer> words = Arrays.asList(1, 3, 5, 7, 9);
//        System.out.println(binarySearch(words, 10));
//        int[] arr = {-10,-8,-2,1,2,5,6};
//        System.out.println(Arrays.toString(twoSum(arr, 0)));

//        int[] height = {1,8,6,2,5,4,8,3,7};
//        System.out.println(maxArea(height));
//        int[] nums = {-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6};
//        List<List<Integer>> lists = threeSum(nums);
//        System.out.println(lists);

        System.out.println(kmpSearch("AAAAABABCDDD", "ABABC"));
        System.out.println(sundaySearch("AAAAABABCDDD", "ABABC"));
    }

    public static int sundaySearch(String str, String pattern) {
        int sLen = str.length();
        int pLen = pattern.length();

        // 方法一：这里是构建一个pattern中所有元素的最后出现位置表，其目的是用来计算窗口在str上偏移位数，也可以直接保存偏移数
        Map<Character, Integer> table = new HashMap<>();
        for (int i = 0; i < pLen; i++) {
            table.put(pattern.charAt(i), i);
        }
        // 方法二：保存偏移位数
        Map<Character, Integer> offsetTable = new HashMap<>();
        for (int i = 0; i < pLen; i++) {
            offsetTable.put(pattern.charAt(i), pLen - i);
        }

        int i = 0;
        while (i + pLen <= sLen ) {
            int j = 0;
            while (j < pLen && str.charAt(i + j) == pattern.charAt(j)) {
                j++;
            }

            if (j == pLen) {
                return i;
            }

            int nextIndex = i + pLen;
            if (nextIndex >= sLen) return -1;
            // 这里计算得到偏移量
//            Integer index = table.get(str.charAt(nextIndex));
//            i += index == null ? pLen + 1 : pLen - index;
            // 直接使用偏移表
            i += offsetTable.getOrDefault(str.charAt(nextIndex), pLen + 1);
        }

        return -1;
    }

    public static int kmpSearch(String str, String pattern) {
        int[] next = new int[pattern.length()];
        int j = 0;// 记录最大前后缀长度
        for (int i = 1; i < pattern.length(); i++) {
            // 减小当前最大前后缀长度，所以j必须大于0
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }

            // j=0才需要这一步，不然就可以j++了
            if (pattern.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            next[i] = j;
        }

        j = 0;
        for (int i = 0; i < str.length(); i++) {
            while (j > 0 && str.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }

            if (str.charAt(i) == pattern.charAt(j)) {
                j++;
            }

            if (j == pattern.length()) {
                return i - pattern.length() + 1;
            }
        }

        return -1;
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;

        int i = 0;
        while (i < n - 2) {
            while (i < nums.length - 1 && nums[i] == nums[i + 1]) i++;

            int first = nums[i];

            int left = i + 1;
            int right = n - 1;
            while (left < right) {
                int sum = nums[left] + nums[right] + first;
                if(sum == 0) {
                    result.add(Arrays.asList(first, nums[left], nums[right]));
                    while(left < right && nums[left] == nums[left+1]){left++;}
                    while(left < right && nums[right] == nums[right-1]){right--;}
                    left++;
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
            i++;
        }

        return result;
    }

    public static int maxArea(int[] height) {
        // 思路一，要想桶装的多，要么底大，要么桶深
        int width = height.length - 1; // 桶底宽度

        int left = 0;
        int right = width;
        int area;
        int ans = 0;
        while (left < right) {
            area = (right- left) * Math.min(height[left], height[right]);
            ans = Math.max(ans, area);
            if (height[left] < height[right]) {
                int hL = height[left];
                do {
                    left++;
                } while (left < right && hL >= height[left]);
            } else {
                int hR = height[right];
                do {
                    right--;
                } while (left < right && hR >= height[right]);
            }
        }

        return ans;
    }


    public static int[] twoSum(int[] numbers, int target) {
        if (numbers.length < 2) {
            return new int[0];
        }

//        int i = 0;
//        int j = 1;

//        int len = numbers.length;
//        while (i < len && j < len) {
//            if (numbers[i] + numbers[j] == target) {
//                int[] result = new int[2];
//                result[0] = i + 1;
//                result[1] = j + 1;
//                return result;
//            }
//
//            // 如果当前值结果大于target，或者已经逼到最后一个了
//            if (numbers[i] + numbers[j] > target || j == numbers.length - 1) {
//                i += 1;
//                j = i + 1;
//                continue;
//            }
//
//            j++;
//        }

//        for (int k = 0; k < numbers.length - 1; k++) {
//            int index = binarySearch(numbers, k, numbers[k], target);
//            if (index != -1) {
//                return new int[]{k + 1, index + 1};
//            }
//        }

        int left = 0;
        int right = numbers.length - 1;

        while (left < right) {
            if (numbers[left] + numbers[right] == target) {
                return new int[]{left + 1, right + 1};
            }
            if (numbers[left] + numbers[right] > target) {
                right--;
            } else {
                left++;
            }
        }

        return new int[0];
    }

    public static int binarySearch(int[] arr, int index, int num, int target) {
        int start = index + 1;
        int end = arr.length - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;
            int term = num + arr[mid];
            if (term == target) {
                return mid;
            }

            if (term < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        return -1;
    }

    /**
     * 基于二分查找实现的方式
     * @param s
     * @param t
     * @return
     */
    public static boolean isSubsequence_Binary(String s, String t) {
        Map<Character, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            map.computeIfAbsent(c, k -> new ArrayList<Integer>());
            map.get(c).add(i);
        }

        int index = -1;
        int i = 0;
        while (i < s.length()) {
            char c = s.charAt(i);
            List<Integer> list = map.get(c);
            if (list == null) {
                return false;
            }

            // 这是普通写法，换成二分查找可以更快出结果
//            int b = -1;
//            for(int a: list){
//                if (a > index) {
//                    b = a;
//                    break;
//                }
//            }

            int b = binarySearch(list, index);

            if (b == -1) {
                return false;
            }

            index = b;
            i++;
        }

        return true;
    }

    /**
     * 通过二分法查找第一个比index大的数
     * @param list
     * @param index
     * @return
     */
    public static int binarySearch(List<Integer> list, int index) {
        int left = 0;
        int right = list.size() - 1;
        int mid;
        int result = -1;
        while (left <= right) {
            mid = (right + left) / 2;
            if (list.get(mid) > index) {
                result = mid; // 记录下当前值，继续寻找更小的比index大的位置
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return result == -1 ? -1 : list.get(result);
    }

    /**
     * t去掉一些字符后，是不是可以等于s---动态规划法
     * @param s
     * @param t
     * @return
     */
    public static boolean isSubsequence_DP(String s, String t) {
        int[][] table = buildTable(t);
        int i = 0;
        int j = 0;
        while (i < s.length() && j < t.length()) {
            int index = table[j][s.charAt(i) - 'a'];
            if (index == t.length()) {
                return false;
            }
            i++;
            j = index + 1;
        }

        return i == s.length();
    }

    private static int[][] buildTable(String t) {
        int a = 97;// ASCII中a的数字表示
        int width = 26;// 英文字母数
        int[][] tables = new int[t.length() + 1][width];

        int tLen = t.length();
        // 给最后一行设置成越界的情况，即t长度
        for (int i = 0; i < width; i++) {
            tables[tLen][i] = tLen;
        }

        for (int i = tLen - 1; i >= 0; i--) {
            char c = t.charAt(i);

            // 预设成都不存在的时的位置
            System.arraycopy(tables[i + 1], 0, tables[i], 0, width);

            // 如果存在设置成位置
            for (int j = i; j < tLen; j++) {
                if (t.charAt(j) == c) {
                    tables[i][t.charAt(j) - a] = i;
                }
            }
        }

        return tables;
    }

    /**
     * t去掉一些字符后，是不是可以等于s---普通方法
     * @param s 段字符串
     * @param t 长字符串
     * @return
     */
    public static boolean isSubsequence(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        int i = 0;
        int j = 0;

        while (i < sLen && j < tLen) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }
            j++;
        }

        return i == sLen;
    }


    /**
     * 是否是回环字符春串
     * @param s 输入字符串
     * @return
     */
    public static boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }

            while (left < right && !Character.isLetterOrDigit(s.charAt(right))){
                right--;
            }

            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                return false;
            }
            left++; right--;
        }
        return true;
    }

    public static List<String> fullJustify(String[] words, int maxWidth) {
        int minSpace = 0;
        int start = 0;
        int end = 0;
        int index = 0;
        int i = - 1;

        List<String> result = new ArrayList<>();
        while (index <= maxWidth && i + 1 <= words.length) {
            // 如果超长，那么拼接字符串
            if (i + 1 == words.length ||
                    index + words[i + 1].length() + (index > 0 ? 1 : 0) + minSpace > maxWidth) {
                int[] space = space(maxWidth, end - start, index);

                StringBuilder s = new StringBuilder();
                if (i + 1 == words.length) {
                    // 最后一行
                    for (int j = start; j < end; j++) {
                        s.append(words[j]);
                        if (j != end - 1) {
                            // 如果最后一行但不是最后一个，只加一个
                            s.append(" ");
                        } else {
                            // 如果时最后一行最后一个，那么剩余所有空格加末尾
                            int length = s.toString().length();
                            for (int k = 0; k < maxWidth - length; k++) {
                                s.append(" ");
                            }
                        }
                    }
                } else {
                    int k = 0;
                    for (int j = start; j < end; j++) {
                        s.append(words[j]);
                        // 如果只有一个时加空格，或者是不是最后一个时加空格
                        if (start == end - 1 || j != end - 1) {
                            s.append(buildSpace(space[k++]));
                        }
                    }
                }

                if (s.toString().isEmpty()) break;
                result.add(s.toString());

                start=end;
//                end = start;
                index = 0;
                minSpace = 0;
            } else {
                i= i + 1; //计总数
                index += words[i].length(); // 长度相加
                minSpace = end - start; //最小空格数
                end++;// 窗口+1
            }
        }

        return result;
    }

    public static String buildSpace(int space) {
        if (space == 0) {
            return "";
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < space; i++) {
            sb.append(" ");
        }

        return sb.toString();
    }

    public static int[] space(int maxWidth, int wordSize, int index) {
        int s = maxWidth - index;
        int space = wordSize - 1;

        int[] result = new int[maxWidth];
        if (space == 0) {
            result[0] = s;
            return result;
        }
        int i = s / space;
        int j = s % space;

        for (int k = 0; k < space; k++) {
            result[k] = i;
        }

        for (int k = 0; k < j; k++) {
            result[k] += 1;
        }

        return result;
    }

    public static int divide(int dividend, int divisor) {
        if (divisor == 1)
            return dividend;
        if (dividend == 0)
            return 0;
        if (divisor == -1) {
            if (dividend == Integer.MIN_VALUE)
                return Integer.MAX_VALUE;
            return -dividend;
        }

        // 确定符号
        boolean flag = (dividend > 0) == (divisor > 0);

        int a = -Math.abs(dividend);
        int d = -Math.abs(divisor);

        int res = div(a, d);

        return flag ? res : -res;
    }

    private static int div(long a, long b) {
        if (a > b) {
            return 0;
        }

        int count = 1;
        long tb = b;
        while ((tb + tb) > a && tb + tb< 0) {
            tb = tb + tb;
            count = count + count; // 这里就是绝妙的地方！！！！！
        }

        return count + div(a - tb, b);
    }


}
